"""
邻接矩阵是一个二维数组，通过矩阵的行和列表示图中的顶点，矩阵元素 matrix[i][j] 表示顶点 i 到顶点 j 是否存在边（以及边的权重，适用于带权图）。

两种表示方式的对比
特性	            邻接矩阵	                                        邻接表
空间复杂度	    O (n²)（n 为顶点数）	                            O (n + m)（m 为边数）
适合场景	        稠密图（边多）	                                    稀疏图（边少）
查找边效率	    O (1)（直接访问矩阵元素）	                        O (k)（k 为邻接顶点数）
遍历邻接顶点	    O (n)（需遍历整行）	                             O (k)（直接遍历列表）

根据题目需求选择合适的表示方式即可，实际考试中邻接表更常用（空间效率高）。

"""

class GraphMatrix:
    def __init__(self, num_vertices, directed=False):
        """
        初始化邻接矩阵
        :param num_vertices: 顶点数量
        :param directed: 是否为有向图（默认无向图）
        """
        self.num_vertices = num_vertices  # 顶点数量
        self.directed = directed  # 是否为有向图
        """
        初始化矩阵（0表示无连接，1表示有连接，带权图可存储权重值）
        创建一个大小为 顶点数×顶点数 的方阵，初始时所有元素为 0（表示所有顶点之间都没有边），后续通过修改矩阵元素的值来表示顶点间的连接关系。
        内层 [0 for ...] 加中括号：内层是一个列表推导式，[0 for _ in range(num_vertices)] 直接生成一个包含 num_vertices 个 0 的列表（即矩阵的一行），所以必须用中括号 [] 表示这是一个列表。
        外层 for ... 不加中括号：外层的 for _ in range(num_vertices) 是循环逻辑，作用是 “将内层生成的列表重复 num_vertices 次”，最终组合成一个二维列表（矩阵）。它本身不是列表元素的定义，因此不需要中括号。
        比如当 num_vertices=4 时：
        内层先生成 [0,0,0,0]（一行）。
        外层循环 4 次，把这一行重复 4 次，得到 [[0,0,0], [0,0,0], [0,0,0], [0,0,0]]。
        """
        self.matrix = [[0 for _ in range(num_vertices)] for _ in range(num_vertices)]


    def add_edge(self, v1, v2, weight=1):
        """添加边（v1到v2，无向图则会同时添加v2到v1）"""
        if 0 <= v1 < self.num_vertices and 0 <= v2 < self.num_vertices:
            #matrix是一个二维矩阵
            self.matrix[v1][v2] = weight
            if not self.directed:  # 无向图对称 即如果该图是无向图，则给matrix[v2][v1]也附上值
                self.matrix[v2][v1] = weight
        else:
            raise ValueError("顶点编号超出范围")

    def remove_edge(self, v1, v2):
        """删除边(逻辑上删除，即把矩阵对应位置的值置为0)"""
        if 0 <= v1 < self.num_vertices and 0 <= v2 < self.num_vertices:
            self.matrix[v1][v2] = 0
            if not self.directed:
                self.matrix[v2][v1] = 0
        else:
            raise ValueError("顶点编号超出范围")

    def get_neighbors(self, v):
        """获取顶点v的所有邻接顶点"""
        if 0 <= v < self.num_vertices:
            """
            这行列表推导式的执行顺序遵循 “循环 → 判断 → 收集” 的逻辑，具体步骤如下：
            执行顺序拆解：
            先执行外层循环 for i in range(self.num_vertices)生成一个从 0 到 self.num_vertices - 1 的序列（即所有顶点的编号），并逐个取出变量 i。例如：若 self.num_vertices=4，则 i 依次取 0,1,2,3。
            对每个 i 执行条件判断 if self.matrix[v][i] != 0检查邻接矩阵中 “顶点 v 的行、顶点 i 的列” 对应的元素是否不等于 0：
            收集满足条件的 i 到列表中把所有通过条件判断的 i 依次放入列表，最终返回这个列表。
            总结：
            整体顺序是 “遍历所有顶点编号 → 筛选出与 v 有边的顶点 → 组成列表返回”，本质是对 “顶点是否邻接” 的条件筛选。
            """
            return [i for i in range(self.num_vertices) if self.matrix[v][i] != 0]
        else:
            raise ValueError("顶点编号超出范围")

    def display(self):
        """打印邻接矩阵"""
        #会遍历矩阵中的每一行（row 就是矩阵中的某一行，是一个一维列表）。
        for row in self.matrix:
            #会将当前行的内容打印出来。
            print(row)


# 示例：创建无向图并测试
if __name__ == "__main__":

    graph = GraphMatrix(4)
    graph.add_edge(0, 1)  # 顶点0-1
    graph.add_edge(0, 2)  # 顶点0-2
    graph.add_edge(1, 3)  # 顶点1-3
    graph.add_edge(2, 3)  # 顶点2-3
    print("邻接矩阵：")
    graph.display()
    print("\n顶点0的邻接顶点：", graph.get_neighbors(0))  # 输出 [1, 2]